package d2_final_exam.d6_sixth_question;

import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;
import java.util.stream.Collectors;

public class MyLinkedList<E> {
    // 封装一个链表
    Node<E> head = null;

    /**
     * 定义了一个私有的内部类，作为链表的结点。
     */
    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public Node<E> add(E e) {
        if (head == null) {
            head = new Node(e, null);
        } else {
            // 往后面插入结点。（尾插法）
            Node<E> temp = head;
            // 让temp走到尾部结点
            while (temp.next != null) {
                temp = temp.next;
            }
            // 把当前结点创建出来，加入到尾部结点
            temp.next = new Node(e, null);
        }
        return head;
    }

    //3、开发一个mergeSort方法, 支持将两个升序排序的链表, 合并成一个链表
    //分析: 需要两个链表的头指针传进来, 然后获取里面的所有数据, 存入到集合,然后创建新链表,存数据
    public  Node<E> mergeSort(Node<E> head1, Node<E> head2) {
        //2.先做极端判断
        if (head1 == null || head2 == null) {
            System.out.println(head2);
            System.out.println(head1);
            return null;//直接结束,不进行
        }
        //1.创建一个集合,存储两个链表的数据
        List<E> datas = new ArrayList<>();
        //4. 首先将链表的首元素添加到集合中
//        Collections.addAll(datas, head1.data, head2.data);
        datas.add(head1.data);
        //3.开始遍历
        while (head1.next != null) {
            head1 = head1.next;
            datas.add(head1.data);
        }
        datas.add(head2.data);

        while (head2.next != null) {
            head2 = head2.next;
            datas.add(head2.data);
        }
        //6.首先先将链表进行排序
        List<E> collect = datas.stream().sorted().collect(Collectors.toList());
        System.out.println(collect);
        //7.创建一个节点用于存储,新链表的头头节点
        Node<E> NewHead = null;
        //5.进行创建一个链表 -->遍历集合将元素,存入到新链表中
        for (E e : collect) {
            NewHead = add(e);
        }
        System.out.println(forEach(NewHead));

        //8.最后将头节点,进行返回
        return NewHead;

    }

    //1、开发一个sort方法, 对两个链表分别排序
    //感觉要进行头指针的返回,便于后续进行遍历-->顺着头指正往下找
    //1.需要参数,链表,
    //2.思路就是用一个集合,请按照顺序取出全部元素,然后然后进行排序,然后再遍历出入链表中
    public void sort(Node<E> head) {
        //首先做极端判断
        if (head == null || head.next == null) {
            return;
        }
        //3.首先保护头指正
        Node<E> firstNode = head;
        //4.创建一个集合,用于存储链表中的元素
        List<E> data = new ArrayList<>();
        data.add(firstNode.data);

        //5.开始循环,获取链表中的所有元素
        while (firstNode.next != null) {
            //8.想要将头指针, 的元素存入的集合中去
//            data.add(firstNode.data);
            //6.让循环跑起来
            firstNode = firstNode.next;
            //7.开始将遍历到的节点的元素存入到集合中去
            data.add(firstNode.data);


        }

        //10.再次将firstNode置成head
//        firstNode = head;

        //9.对集合进行排序, 使用工具类Collections
//        Collections.sort(data);
        List<E> dataS = data.stream().sorted().collect(Collectors.toList());
//        System.out.println(dataS);
       /* datas.forEach(d -> {
            firstNode.data = d;
        });*/
        //11.开始循环 -->直接进行遍历集合即可
       /* for (int i = 0; i < dataS.size(); i++) {
            E e = dataS.get(i);
//            assert firstNode != null;
            head.data = e;
            head = head.next;
        }*/
        for (E e : dataS) {
            //            assert firstNode != null;
            head.data = e;
            head = head.next;
        }
//        return head;
    }

    //2、开发一个遍历的方法, 传入一个头指针, 进行遍历
    public String forEach(Node<E> head) {
        //3.首先进行极端判断,如果是空或者长度是1,都是直接进行打印
        if (head == null || head.next == null) {
//            System.out.println(head);
            return head + "";
        }

        //1.创建一个StringJoiner, 进行输出格式
        StringJoiner sj = new StringJoiner("-> ", "[", "]");
        sj.add(head.data + "");
        //2.开始循环,遍历所有数据,然后添加到容器中
        while (head.next != null) {
            //4.首先将数据存入到容器中
            head = head.next;
            sj.add(head.data + "");
        }

        //5.最后将数据,进行返回

        return sj.toString();
    }
}